package cn.wit.testalgorithms;
/**
 * 35.插入位置
 * 优化算法，使用二分搜索
 * @author 16604
 *
 */
public class DemoOptimisticSearchInsertPosition {

	public static void main(String[] args) {

		int[] data = { 1,3,5,6 };
		int Key = 0;

		demoBinarySearch(data, Key);
	}
	
	public static void demoBinarySearch(int[] data, int Key) {

		// 得先找出中间值,这里还得定义一个左边变量与右边变量
		int left = 0;
		int mid = 0;
		int right = data.length - 1;
		boolean flag = false;

		while (right >= left) {
			// 然后去判断当前min与Key得值
			// 中间元素得值比所要查询得值要大
			mid = (left + right) / 2;

			if (Key < data[mid]) {
				// 注意：这里就一定要更新每次得左边变量，以及中间值
				right = mid - 1;
				//边界判断
				if (right < left)
					break;
			}

			// 中间元素得值比所要查询得值要小
			if (Key > data[mid]) {
				// 注意：这里就一定要更新每次得右边变量，以及中间值
				left = mid + 1;
				//边界判断
				if (right < left)
					break;
			}

			// 中间元素等于所要查询得值
			if (data[mid] == Key) {
				//查询到
				flag = true;
				break;
			}
		}
		
		if (flag == true) {
			System.out.println(mid);
		}
		if(Key>data[data.length-1]) {
			System.out.println(data.length);
		}else {
			System.out.println(mid);
		}
		
	}
}
